package com.bjwen;

import java.util.List;

public class FFt {
    final double PI = 3.14159265359;
    Complex[] rotationFactors;
    Complex[] array;
    int point;
    int times;//总共步数:M

    FFt(List<Double> list) {
        double[] doubleList = reSort(list);
        this.point = list.size();
        array = new Complex[point];
        for (int i = 0; i < point; i++) {
            array[i] = new Complex(doubleList[i]);
        }
        rotationFactors = new Complex[point / 2];
        generateRotationFactors();
        times = (int) (Math.log(point) / Math.log(2));
    }


    public Complex[] proceed() {

        for (int stage = 0; stage < times; stage++) {// stage : L
            int length = (int) Math.pow(2, stage + 1);//单个蝶形运算单元的长度
            for (int j = 0; j < point; j += length) {
                butterflyUnit(j, length, stage + 1);
            }
        }
        return array;
    }

    private void butterflyUnit(int start, int length, int stage) {
        int[] k = new int[(int) Math.pow(2, stage - 1)];
        for (int i = 0; i < k.length; i++) {
            k[i] = i * (int) Math.pow(2, times - stage);
        }
        int i = 0;
        length /= 2;
        while (i < length) {
            butterfly(start, start + length, k[i]);
            start++;
            i++;
        }
    }

    private void butterfly(int c, int d, int k) {
        Complex a = new Complex(array[c]);
        Complex b = new Complex(array[d]);
        b.multiply(rotationFactors[k], false);
        array[c] = a.add(b, true);
        array[d] = a.minus(b, true);
    }

    private void generateRotationFactors() {
        for (int i = 0; i < point / 2; i++) {
            double index = 2 * PI * (double) i / (double) point;
            rotationFactors[i] = new Complex(Math.cos(index)
                    , -1 * Math.sin(index));
        }
    }

    private double[] reSort(List<Double> list) {
        double[] temp = new double[list.size()];
        String d = Integer.toBinaryString(list.size() - 1);
        int maxLength = d.length();
        for (int i = 0; i < list.size(); i++) {
            StringBuilder s = new StringBuilder(Integer.toBinaryString(i));
            while (s.length() != maxLength) {
                s.insert(0, '0');
            }
            String string = s.reverse().toString();
            int j = Integer.parseInt(string, 2);
            temp[j] = list.get(i);
        }
        return temp;
    }

}
